home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / graphic / frasr182.zip / DECODER.C < prev    next >
C/C++ Source or Header  |  1992-07-15  |  14KB  |  449 lines
  1. /* DECODE.C - An LZW decoder for GIF
  2.  * Copyright (C) 1987, by Steven A. Bennett
  3.  *
  4.  * Permission is given by the author to freely redistribute and include
  5.  * this code in any program as long as this credit is given where due.
  6.  *
  7.  * In accordance with the above, I want to credit Steve Wilhite who wrote
  8.  * the code which this is heavily inspired by...
  9.  *
  10.  * GIF and 'Graphics Interchange Format' are trademarks (tm) of
  11.  * Compuserve, Incorporated, an H&R Block Company.
  12.  *
  13.  * Release Notes: This file contains a decoder routine for GIF images
  14.  * which is similar, structurally, to the original routine by Steve Wilhite.
  15.  * It is, however, somewhat noticably faster in most cases.
  16.  *
  17.  == This routine was modified for use in FRACTINT in two ways.
  18.  ==
  19.  == 1) The original #includes were folded into the routine strictly to hold
  20.  ==    down the number of files we were dealing with.
  21.  ==
  22.  == 2) The 'stack', 'suffix', 'prefix', and 'decoderline' arrays were changed from
  23.  ==    static and 'malloc()'ed to external only so that the assembler
  24.  ==    program could use the same array space for several independent
  25.  ==    chunks of code.    Also, 'stack' was renamed to 'dstack' for TASM
  26.  ==    compatibility.
  27.  ==
  28.  == 3) The 'out_line()' external function has been changed to reference
  29.  ==    '*outln()' for flexibility (in particular, 3D transformations)
  30.  ==
  31.  == 4) A call to 'keypressed()' has been added after the 'outln()' calls
  32.  ==    to check for the presenc of a key-press as a bail-out signal
  33.  ==
  34.  == (Bert Tyler and Timothy Wegner)
  35.  */
  36.  
  37. /* Rev ??/??/?? - Initial Release
  38.  * Rev 01/02/91 - Revised by Mike Gelvin
  39.  *                    altered logic to allow newcode to input a line at a time
  40.  *                    altered logic to allow decoder to place characters
  41.  *                        directly into the output buffer if they fit
  42. */
  43.  
  44. /***** C Library Includes ***********************************************/
  45. #include <stdio.h>
  46.  
  47. /***** Application Includes *********************************************/
  48. #include "prototyp.h"
  49.  
  50. /***** Application Function Prototypes **********************************/
  51. static short get_next_code(void);
  52.  
  53. /* extern short out_line(pixels, linelen)
  54.  *     UBYTE pixels[];
  55.  *     short linelen;
  56.  *
  57.  *   - This function takes a full line of pixels (one byte per pixel) and
  58.  * displays them (or does whatever your program wants with them...).  It
  59.  * should return zero, or negative if an error or some other event occurs
  60.  * which would require aborting the decode process...  Note that the length
  61.  * passed will almost always be equal to the line length passed to the
  62.  * decoder function, with the sole exception occurring when an ending code
  63.  * occurs in an odd place in the GIF file...  In any case, linelen will be
  64.  * equal to the number of pixels passed...
  65.  */
  66. int (*outln)(BYTE *,int) = out_line;
  67.  
  68. /***** Local Static Variables *******************************************/
  69. /* Various error codes used by decoder
  70.  * and my own routines...   It's okay
  71.  * for you to define whatever you want,
  72.  * as long as it's negative...  It will be
  73.  * returned intact up the various subroutine
  74.  * levels...
  75.  */
  76. #define OUT_OF_MEMORY -10
  77. #define BAD_CODE_SIZE -20
  78. #define READ_ERROR -1
  79. #define WRITE_ERROR -2
  80. #define OPEN_ERROR -3
  81. #define CREATE_ERROR -4
  82.  
  83. #define MAX_CODES   4095
  84.  
  85. #define NOPE 0
  86. #define YUP -1
  87.  
  88. static short curr_size;            /* The current code size */
  89.  
  90. #ifndef XFRACT
  91. static short far sizeofstring[MAX_CODES+1];
  92. #else
  93. static short sizeofstring[MAX_CODES+1];    /* size of string list */
  94. #endif
  95.  
  96. /* The following static variables are used
  97.  * for seperating out codes
  98.  */
  99. static short navail_bytes;        /* # bytes left in block */
  100. static short nbits_left;        /* # bits left in current byte */
  101. static BYTE byte_buff[257];    /* Current block, reuse shared mem */
  102. static BYTE *pbytes;        /* Pointer to next byte in block */
  103. static unsigned short ret_code;
  104.  
  105. static short code_mask[13] = {
  106.      0,
  107.      0x0001, 0x0003,
  108.      0x0007, 0x000F,
  109.      0x001F, 0x003F,
  110.      0x007F, 0x00FF,
  111.      0x01FF, 0x03FF,
  112.      0x07FF, 0x0FFF
  113.      };
  114.  
  115. /***** External Variables ***********************************************/
  116. /* extern short bad_code_count;
  117.  *
  118.  * This value is the only other global required by the using program, and
  119.  * is incremented each time an out of range code is read by the decoder.
  120.  * When this value is non-zero after a decode, your GIF file is probably
  121.  * corrupt in some way...
  122.  */
  123. extern short bad_code_count;
  124.  
  125. /* whups, here are more globals, added by PB: */
  126. extern short skipxdots; /* 0 to get every dot, 1 for every 2nd, 2 every 3rd, ... */
  127. extern short skipydots; /* ditto for rows */
  128.  
  129. /*
  130. I removed the LOCAL identifiers in the arrays below and replaced them
  131. with 'extern's so as to declare (and re-use) the space elsewhere.
  132. The arrays are actually declared in the assembler source.
  133.                         Bert Tyler
  134. */
  135. extern BYTE dstack[MAX_CODES + 1];            /* Stack for storing pixels */
  136. extern BYTE suffix[MAX_CODES + 1];            /* Suffix table */
  137. extern unsigned short prefix[MAX_CODES + 1];        /* Prefix linked list */
  138. extern BYTE decoderline[2];                /* decoded line goes here */
  139.  
  140.  
  141. /* The reason we have these separated like this instead of using
  142.  * a structure like the original Wilhite code did, is because this
  143.  * stuff generally produces significantly faster code when compiled...
  144.  * This code is full of similar speedups...  (For a good book on writing
  145.  * C for speed or for space optimization, see Efficient C by Tom Plum,
  146.  * published by Plum-Hall Associates...)
  147.  */
  148.  
  149.  
  150. /***** Program **********************************************************/
  151. /* short decoder(linewidth)
  152.  *    short linewidth;            * Pixels per line of image *
  153.  *
  154.  * - This function decodes an LZW image, according to the method used
  155.  * in the GIF spec.  Every *linewidth* "characters" (ie. pixels) decoded
  156.  * will generate a call to out_line(), which is a user specific function
  157.  * to display a line of pixels.  The function gets its codes from
  158.  * get_next_code() which is responsible for reading blocks of data and
  159.  * seperating them into the proper size codes.    Finally, get_byte() is
  160.  * the global routine to read the next byte from the GIF file.
  161.  *
  162.  * It is generally a good idea to have linewidth correspond to the actual
  163.  * width of a line (as specified in the Image header) to make your own
  164.  * code a bit simpler, but it isn't absolutely necessary.
  165.  *
  166.  * Returns: 0 if successful, else negative.  (See ERRS.H)
  167.  *
  168.  */
  169. short decoder( short linewidth)
  170. {
  171.     BYTE *sp;
  172.     short code;
  173.     short old_code;
  174.     short ret;
  175.     short c;
  176.     short size;
  177.     short i;
  178.     short j;
  179.     short fastloop;
  180.     short bufcnt;                    /* how many empty spaces left in buffer */
  181.     short xskip;
  182.     short slot;                        /* Last read code */
  183.     short newcodes;                    /* First available code */
  184.     BYTE *bufptr;
  185.     short yskip;
  186.     short top_slot;                    /* Highest code for current size */
  187.     short clear;                    /* Value for a clear code */
  188.     short ending;                    /* Value for a ending code */
  189.     BYTE out_value;
  190.  
  191.  
  192.     /* Initialize for decoding a new image...
  193.     */
  194.  
  195.     if ((size = get_byte()) < 0)
  196.         return(size);
  197.     if (size < 2 || 9 < size)
  198.         return(BAD_CODE_SIZE);
  199.  
  200.     curr_size = size + 1;
  201.     top_slot = 1 << curr_size;
  202.     clear = 1 << size;
  203.     ending = clear + 1;
  204.     slot = newcodes = ending + 1;
  205.     navail_bytes = nbits_left = sizeofstring[slot] = xskip = yskip
  206.         = old_code = 0;
  207.     out_value = 0;
  208. for (i = 0; i < slot; i++)
  209. {    sizeofstring[i] = 0;
  210. }
  211.     
  212.     /* Initialize in case they forgot to put in a clear code.
  213.      * (This shouldn't happen, but we'll try and decode it anyway...)
  214.     */
  215.  
  216.     /* Set up the stack pointer and decode buffer pointer
  217.     */
  218.     sp = dstack;
  219.     bufptr = decoderline;
  220.     bufcnt = linewidth;
  221.  
  222.     /* This is the main loop.  For each code we get we pass through the
  223.      * linked list of prefix codes, pushing the corresponding "character" for
  224.      * each code onto the stack.  When the list reaches a single "character"
  225.      * we push that on the stack too, and then start unstacking each
  226.      * character for output in the correct order.  Special handling is
  227.      * included for the clear code, and the whole thing ends when we get
  228.      *